#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <vector>

using namespace std;
using LL = long long;
const LL mod = 998244353;
const int N = 65;

LL k1 = 0, k2 = 0;
LL f[N][N];

void init(){
    for(int i = 0; i < N; i ++){
        for(int j = 0; j <= i; j ++){
            if(j == 0) f[i][j] = 1;
            else f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]);
        }
    }
}


void dfs(int n){
    if(n == 0) return;

    if(n == 2) {
        k1 = (k1 + 1) % mod;
        return;
    }


    if(n == 4){
        k1 = (k1 + 3) % mod;
        k2 = (k2 + 2) % mod;

       // cout << k1 << " " << k2 << endl;
        return;
    }

    if(n / 2 >= 4){
        k1 = (k1 + f[n - 4][n/2 - 1]) % mod;
        k1 = (k1 + 3 * f[n - 4][n/2 - 2]) % mod;
        k1 = (k1 + 4 * f[n - 4][n/2 - 3]) % mod;
        k1 = (k1 + f[n - 4][n/2 - 4]) % mod;

        k2 = (k2 + 2 * f[n - 4][n/2 - 2]) % mod;
        k2 = (k2 + 3 * f[n - 4][n/2 - 3]) % mod;
        k2 = (k2 + f[n - 4][n/2 - 4]) % mod;
    }else if(n / 2 >= 3){
        k1 = (k1 + f[n - 4][n/2 - 1]) % mod;
        k1 = (k1 + 3 * f[n - 4][n/2 - 2]) % mod;
        k1 = (k1 + 4 * f[n - 4][n/2 - 3]) % mod;

        k2 = (k2 + 2 * f[n - 4][n/2 - 2]) % mod;
        k2 = (k2 + 3 * f[n - 4][n/2 - 3]) % mod;
    }else if(n / 2 >= 2){
        k1 = (k1 + f[n - 4][n/2 - 1]) % mod;
        k1 = (k1 + 3 * f[n - 4][n/2 - 2]) % mod;

        k2 = (k2 + 2 * f[n - 4][n/2 - 2]) % mod;
    }else if(n / 2 >= 1){
        k1 = (k1 + f[n - 4][n/2 - 1]) % mod;
    }

    dfs(n - 4);
}

int main(){
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init();

    int T;
    cin >> T;

    
    while(T--){
        k1 = 0, k2 = 0;
        int n;
        cin >> n;
        dfs(n);
        cout << k1 << " " << k2 << " 1" << '\n'; 
    }



    return 0;
}